결정 트리

결정 트리는 트리 구조를 사용하여 데이터를 분류하거나 회귀 분석을 수행하는 지도 학습 알고리즘이다. 이 트리는 내부 노드와 단말 노드로 구성되며, 각 내부 노드는 데이터의 특성에 대한 조건(분할 규칙)을 나타낸다. 단말 노드, 즉 리프 노드는 최종 예측값(클래스 라벨이나 회귀 값)을 담당한다. 학습 과정은 데이터를 가장 잘 구분할 수 있는 질문(분할 기준)을 반복적으로 찾아 트리를 성장시키는 것이다.

분할의 핵심 목표는 자식 노드들이 부모 노드보다 더 '순수'해지도록 하는 것이다. 즉, 같은 클래스의 데이터가 한 노드에 모이거나 회귀 값의 분산이 줄어들도록 한다. 이를 위해 각 노드에서 모든 가능한 특성과 그 임계값을 평가하여 최적의 분할 점을 선택한다. 분할 평가는 일반적으로 지니 불순도나 엔트로피(분류 문제), 또는 분산 감소(회귀 문제)와 같은 순도 지표를 사용하여 계산된 정보 이득을 기준으로 한다.

분할 과정은 의사결정 규칙을 생성하며, 이는 if-then-else 규칙 집합으로 해석될 수 있다. 예를 들어, "특성 A의 값이 X 이상인가?"라는 질문에 따라 데이터는 왼쪽 또는 오른쪽 자식 노드로 이동한다. 이 과정은 미리 정의된 정지 조건(예: 노드의 데이터가 모두 같은 클래스이거나, 최대 깊이에 도달하거나, 노드의 샘플 수가 최소값 미만인 경우)이 충족될 때까지 재귀적으로 반복된다.

결정 트리 알고리즘이 노드를 분할할 때, 어떤 기준으로 분할하는 것이 가장 효과적인지를 수치화하여 판단하는 지표를 순도 지표라고 한다. 이 지표는 자식 노드들의 클래스 분포가 얼마나 순수한지, 즉 한 클래스로 잘 모여 있는지를 측정한다. 일반적으로 분할 전의 불순도에서 분할 후의 불순도를 뺀 값, 즉 정보 이득이 큰 분할 기준을 선택한다.

가장 널리 사용되는 순도 지표는 지니 불순도와 엔트로피이다. 지니 불순도는 한 노드에서 무작위로 두 개의 샘플을 뽑았을 때 서로 다른 클래스일 확률을 의미한다. 수식은 $G = 1 - \sum_{i=1}^{c} p_i^2$로 표현되며, 여기서 $p_i$는 해당 노드에서 i번째 클래스의 비율이다. 값이 0이면 해당 노드의 샘플이 모두 동일한 클래스라는 것을 의미하며, 완전히 순수한 상태이다.

엔트로피는 정보 이론에서 비롯된 개념으로, 시스템의 무질서도 또는 불확실성을 측정한다. 결정 트리에서의 엔트로피는 $H = -\sum_{i=1}^{c} p_i \log_2 p_i$로 계산된다. 엔트로피 역시 값이 0이면 완전한 순수성을, 최댓값(예: 이진 분류에서 1)에 가까울수록 클래스 분포가 균등하여 불확실성이 큰 상태를 나타낸다. 알고리즘은 엔트로피 감소량, 즉 정보 이득을 최대화하는 분할을 선택한다.

두 지표 모두 분류 문제에서 노드의 불순도를 정량화하는 데 사용되며, 실제 성능 차이는 크지 않은 경우가 많다. CART 알고리즘은 주로 지니 불순도를, ID3와 C4.5 알고리즘은 엔트로피와 정보 이득을 기본 분할 기준으로 사용한다는 점이 특징이다.

ID3는 로스 퀸란이 1986년에 제안한 결정 트리 학습 알고리즘이다. 이 알고리즘은 정보 이론의 개념, 특히 엔트로피와 정보 이득을 기반으로 하여 트리를 상향식으로 구축하는 것을 핵심으로 한다. ID3는 범주형(명목형) 특성만을 처리할 수 있으며, 수치형 특성에 대한 처리는 지원하지 않는다. 또한, 이 알고리즘은 학습 과정에서 가지치기를 수행하지 않아 과적합되기 쉬운 경향이 있다.

알고리즘의 작동 방식은 다음과 같다. 먼저, 전체 데이터셋을 루트 노드로 시작한다. 각 단계에서 알고리즘은 아직 사용되지 않은 모든 특성에 대해 정보 이득을 계산한다. 정보 이득은 해당 특성으로 데이터를 분할하기 전후의 엔트로피 감소량을 의미하며, 가장 높은 정보 이득을 제공하는 특성을 선택하여 노드를 분할한다. 이 과정은 순수 노드(한 클래스의 샘플만 포함)가 생성되거나 더 이상 분할할 특성이 없을 때까지 재귀적으로 반복된다.

ID3 알고리즘은 그 단순함과 개념적 명료성 덕분에 결정 트리 방법론의 초석이 되었다. 그러나 연속형 값을 처리하지 못하고, 결측치를 다루는 메커니즘이 없으며, 과적합에 취약하다는 한계를 지닌다. 이러한 한계점을 보완하고 발전시킨 후속 알고리즘으로 C4.5와 CART가 등장하게 되었다.

C4.5 알고리즘은 로스 퀸란이 1993년에 제안한 결정 트리 학습 알고리즘으로, 그의 이전 알고리즘인 ID3의 한계를 보완하여 발전시킨 것이다. 이 알고리즘의 핵심 개선점은 연속형 변수를 처리할 수 있는 능력과 결정 트리의 과적합을 줄이기 위한 가지치기 메커니즘의 도입이다.

C4.5는 분할 기준을 선택할 때 정보 이득 대신 정보 이득비를 사용한다. 정보 이득은 값의 범위가 많은 특성(예: 고유 ID)을 선호하는 경향이 있는데, 정보 이득비는 이러한 편향을 보정하여 보다 균형 잡힌 특성 선택을 가능하게 한다[3]. 또한, ID3가 처리하지 못했던 연속적인 수치형 특성(예: 나이, 온도)을 처리하기 위해, 데이터를 정렬한 후 가능한 모든 분할 지점에서 정보 이득비를 계산하여 최적의 임계값을 찾는다.

이 알고리즘의 또 다른 중요한 특징은 사후 가지치기를 수행한다는 점이다. 학습 데이터로 완전한 트리를 성장시킨 후, 통계적 검정을 기반으로 하위 트리를 리프 노드로 대체하여 모델의 복잡도를 줄인다. 이 과정은 학습 데이터에 대한 지나친 맞춤, 즉 과적합을 방지하는 데 기여한다. C4.5는 결측값을 처리하는 메커니즘도 포함하고 있으며, 이는 알려지지 않은 특성 값을 가진 샘플을 분류할 때 사용된다.

C4.5 알고리즘의 출력은 단순한 결정 트리뿐만 아니라, 이해하기 쉬운 의사결정 규칙 집합의 형태로도 변환될 수 있다. 이 알고리즘의 성공과 영향력은 이후 등장한 C5.0 알고리즘과 CART 알고리즘을 포함한 많은 트리 기반 모델의 개발에 기초를 제공했다.

CART는 Classification And Regression Trees의 약자로, 분류와 회귀 모두에 사용할 수 있는 결정 트리 알고리즘이다. ID3나 C4.5 알고리즘과 달리, 이진 분할을 기본으로 한다는 특징을 가진다. 즉, 각 노드는 '예' 또는 '아니오' 질문을 통해 두 개의 자식 노드로만 나뉜다. 이 방식은 트리 구조를 단순화하고 계산 효율성을 높이는 장점이 있다.

CART 알고리즘은 목표 변수의 유형에 따라 다른 순도 지표를 사용하여 최적의 분할 점을 찾는다. 분류 문제에서는 주로 지니 불순도를 최소화하는 방향으로 분할을 진행한다. 회귀 문제에서는 분산 감소, 즉 자식 노드들의 목표 값 분산을 최소화하는 기준을 사용한다. 각 분할에서 가능한 모든 특성과 모든 가능한 분할 임계값을 평가하여 가장 순도를 높이는 단일 분할을 선택하는 탐욕적 알고리즘을 적용한다.

CART로 생성된 트리는 일반적으로 매우 크게 성장한 후, 비용 복잡도 가지치기를 통해 과적합을 방지한다. 이 과정에서는 트리의 크기(노드 수)와 검증 데이터에 대한 오류를 함께 고려한 비용 복잡도 파라미터를 사용하여 서브트리를 제거할지 결정한다. 최종 모델은 교차 검증을 통해 선택된 최적의 가지치기 수준을 가진다.

CART 알고리즘의 주요 특징은 다음과 같이 정리할 수 있다.

이 알고리즘은 그 유연성과 해석의 용이성 덕분에 랜덤 포레스트나 그래디언트 부스팅 머신 같은 고급 앙상블 방법의 기본 구성 요소로 널리 채택되었다.

가지치기는 결정 트리 모델의 과적합을 방지하고 일반화 성능을 높이기 위해 사용되는 정규화 기법이다. 학습 과정에서 생성된 트리의 크기나 복잡도를 사후적으로 줄이는 과정을 의미한다. 가지치기는 주로 학습 데이터에 지나치게 맞춰져 분기한 가지(노드)를 제거하여 모델을 단순화한다.

가지치기 방법은 크게 사전 가지치기와 사후 가지치기로 나뉜다. 사전 가지치기는 트리 성장 중에 최대 깊이 제한이나 노드의 최소 데이터 포인트 수 같은 제약 조건을 두어 성장을 미리 멈추는 방법이다. 반면, 사후 가지치기는 트리가 완전히 성장한 후에 불필요하거나 유의미하지 않은 부분을 제거하는 방식으로, 일반적으로 더 나은 성능을 보인다. 대표적인 사후 가지치기 알고리즘으로는 비용-복잡도 가지치기가 있다. 이 방법은 트리의 오류와 복잡도에 패널티를 부과하는 비용-복잡도 함수를 최소화하는 서브트리를 선택한다.

가지치기의 효과는 검증 세트를 사용하여 평가하는 것이 일반적이다. 가지를 하나씩 제거해가며 검증 세트에 대한 성능이 저하되기 시작하는 지점을 찾거나, 교차 검증을 통해 최적의 트리 크기를 결정한다. 이를 통해 학습 데이터의 노이즈나 특이치에 과도하게 반응한 부분을 제거할 수 있다. 결과적으로 가지치기를 적용한 트리는 더 간결한 규칙을 가지며, 새로운 데이터에 대한 예측 정확도와 해석 가능성이 향상된다.

최대 깊이 제한은 결정 트리 모델의 과적합을 방지하기 위한 가장 직관적인 정규화 기법 중 하나이다. 이 방법은 트리가 성장할 수 있는 최대 레벨(깊이)을 사전에 지정하여 모델의 복잡도를 강제로 제한한다. 깊이가 깊어질수록 트리는 훈련 데이터의 세부적인 패턴과 노이즈까지 학습하게 되어 일반화 성능이 저하되는 경향이 있다. 따라서 적절한 최대 깊이를 설정함으로써 모델이 지나치게 복잡해지는 것을 사전에 차단할 수 있다.

최대 깊이를 설정할 때는 편향-분산 트레이드오프를 고려해야 한다. 너무 낮은 깊이(예: 1 또는 2)는 모델이 데이터의 기본적인 구조조차 학습하지 못하는 과소적합을 초래할 수 있다. 반면, 너무 높은 깊이는 위에서 언급한 대로 과적합을 유발한다. 일반적으로 적절한 최대 깊이는 교차 검증을 통해 결정한다. 모델의 검증 세트에 대한 성능을 평가하면서 깊이를 조정하여 최적의 균형점을 찾는 것이 일반적인 절차이다.

이 기법은 구현이 간단하고 계산 비용이 낮다는 장점이 있어 널리 사용된다. 대부분의 머신러닝 라이브러리에서는 max_depth와 같은 매개변수로 이 기능을 제공한다. 다른 정규화 방법인 가지치기가 트리를 완전히 성장시킨 후 후처리로 노드를 제거하는 방식이라면, 최대 깊이 제한은 트리 성장 과정 자체에 선제적인 제약을 가하는 선제적 방법이다. 두 방법은 종종 함께 사용되어 더 강력한 정규화 효과를 낸다.

랜덤 포레스트는 결정 트리 알고리즘의 단점인 과적합 경향을 줄이고 일반화 성능을 높이기 위해 고안된 앙상블 학습 방법이다. 레오 브레이만에 의해 제안된 이 방법은 배깅과 무작위 특성 선택의 개념을 결합하여 다수의 결정 트리를 구성하고, 그 결과를 종합하여 예측을 수행한다.

랜덤 포레스트의 학습 과정은 크게 두 가지 무작위성을 기반으로 한다. 첫째, 부트스트랩 샘플링을 통해 원본 데이터셋에서 중복을 허용하여 무작위로 추출된 여러 개의 서브셋을 생성한다. 각 결정 트리는 이렇게 생성된 서브셋을 학습 데이터로 사용한다. 둘째, 각 노드에서 분할 기준을 찾을 때, 전체 특성 중 무작위로 선택된 일부 특성만을 후보로 고려한다[4]. 이 과정을 통해 서로 다른 데이터와 특성을 바탕으로 학습된 다수의 트리가 생성된다.

예측 시에는 분류 문제의 경우 다수결 투표를, 회귀 문제의 경우 평균을 취하여 최종 결과를 도출한다. 이는 개별 트리의 예측 오차가 서로 상쇄되도록 하여, 단일 결정 트리보다 훨씬 안정적이고 강건한 성능을 보장한다. 또한, OOB 오차 평가를 통해 추가적인 검증 데이터 없이도 모델의 일반화 성능을 추정할 수 있다는 장점이 있다.

랜덤 포레스트는 다음과 같은 주요 특성을 지닌다.

그래디언트 부스팅 머신(GBM)은 여러 개의 약한 학습기, 주로 결정 트리를 순차적으로 학습하여 강력한 예측 모델을 구성하는 앙상블 학습 기법이다. 이전 트리의 오차를 보완하는 방식으로 새로운 트리를 추가하여 성능을 점진적으로 향상시킨다. 부스팅 알고리즘의 한 종류로, 특히 회귀와 분류 문제에 널리 사용된다.

알고리즘의 핵심은 경사 하강법을 손실 함수 공간에 적용하는 것이다. 먼저, 초기 모델(예: 상수값)을 만든다. 이후 각 반복(부스팅 라운드)에서는 현재 모델의 예측과 실제 값 사이의 오차, 즉 손실 함수의 음의 경사(negative gradient)를 계산한다. 이 계산된 '잔차' 또는 '경사'를 목표값으로 삼아 새로운 결정 트리를 학습시킨다. 새 트리는 이전 모델이 잘못 예측한 부분을 수정하는 방향으로 학습되며, 학습된 트리는 작은 학습률(보통 0.01~0.1)을 곱한 후 기존 모델에 추가된다. 이 과정을 정해진 횟수만큼 반복한다.

GBM의 성능은 여러 하이퍼파라미터에 의해 크게 영향을 받는다. 주요 파라미터로는 트리의 개수(n_estimators), 각 트리의 최대 깊이(max_depth), 학습률(learning_rate), 그리고 트리를 학습할 때 사용할 데이터 샘플의 비율(subsample)이나 특성의 비율(colsample_bytree) 등이 있다. 학습률을 낮게 설정하면 더 많은 트리가 필요하지만 일반적으로 더 나은 일반화 성능을 보인다. 또한, 조기 종료(early stopping) 기능을 활용하여 검증 세트 성능이 더 이상 향상되지 않을 때 학습을 중단함으로써 효율성과 과적합 방지를 동시에 달성할 수 있다.

GBM은 XGBoost, LightGBM, CatBoost와 같은 고도로 최적화된 라이브러리의 등장으로 실무에서 가장 강력하고 인기 있는 머신러닝 알고리즘 중 하나가 되었다. 이 라이브러리들은 정규화 항 추가, 결측값 처리 최적화, 범주형 변수 자동 처리 등의 고급 기능을 제공하며, 대규모 데이터셋에서도 뛰어난 속도와 정확도를 보인다.

결정 트리 모델은 학습 과정에서 각 특성이 목표 변수를 예측하는 데 기여한 정도를 정량적으로 평가할 수 있다. 이 평가 결과를 특성 중요도라고 부르며, 모델 해석과 특성 선택에 유용하게 활용된다.

특성 중요도를 계산하는 일반적인 방법은 해당 특성이 데이터를 분할하는 기준으로 사용되었을 때, 불순도(예: 지니 불순도 또는 엔트로피)가 감소한 양을 누적하는 것이다. 각 노드에서의 불순도 감소량은 해당 노드의 샘플 가중치와 곱해져 전체 트리에 대한 기여도로 합산된다. 최종적으로 모든 특성의 중요도 합이 1이 되도록 정규화하여 상대적 중요도를 파악한다.

이 분석 결과는 특성 공학에 직접적인 인사이트를 제공한다. 중요도가 매우 낮은 특성은 모델 성능에 거의 영향을 미치지 않으므로 제거하여 모델을 단순화할 수 있다. 또한, 도메인 지식과 상반된 중요도 순위가 나올 경우 데이터 전처리 과정이나 특성 자체에 문제가 있을 수 있음을 시사한다. 랜덤 포레스트나 그래디언트 부스팅 같은 트리 기반 앙상블 학습 방법에서는 개별 트리들의 특성 중요도를 평균내어 더욱 안정적인 평가를 얻는다.

결정 트리의 결정 경계는 모델이 입력 공간을 어떻게 분할하는지를 직관적으로 보여준다. 각 내부 노드의 분할 규칙은 하나의 특성과 그 임계값을 기준으로 공간을 두 부분으로 나누며, 이 과정이 반복되어 최종적으로 다차원 공간이 여러 개의 직사각형 영역(리프 노드에 해당)으로 분할된다. 이러한 경계는 축에 평행한 선분들로 구성되기 때문에 해석이 용이하다는 장점이 있다.

시각화는 주로 두 개의 입력 특성(X1, X2)을 선택한 2차원 평면에서 수행된다. 각 리프 노드가 할당한 클래스 레이블에 따라 영역에 색상을 칠하고, 내부 노드의 분할 조건에 해당하는 수직선 또는 수평선을 그려 결정 경계를 나타낸다. 아래 표는 간단한 예시 데이터에 대한 결정 트리의 분할 과정과 그에 따른 결정 경계를 보여준다.

고차원 데이터의 경우 주성분 분석(PCA)이나 t-SNE 같은 차원 축소 기법을 먼저 적용하여 2차원으로 투영한 후 결정 경계를 시각화하기도 한다. 그러나 이 경우 원본 특성 공간의 축에 평행한 경계라는 본래 특성이 왜곡될 수 있음에 유의해야 한다.

결정 경계 시각화는 모델의 복잡도를 진단하는 데 유용한 도구이다. 깊이가 얕은 트리는 넓고 단순한 직사각형 영역을 만들지만, 깊이가 깊어지고 가지치기가 충분히 이루어지지 않으면 훈련 데이터의 작은 변동까지 잡아내며 구불구불하고 복잡한 경계를 형성한다. 이는 과적합의 징후로 해석될 수 있다. 따라서 시각화를 통해 모델이 데이터의 일반적인 패턴을 잘 학습했는지, 아니면 노이즈에 과민 반응하는지를 판단하는 데 도움을 얻을 수 있다.